/*
time:20201028 19:54 PM
key:1.从结果来看，第一个指针的next在最后的倒置中应该指向NULL。所以在第一次递归遍历就要将第一个指针的next指向NULL
	这里设计了一个在递归里只会执行一次的bool函数。
user：ldc
*/
#include <math.h>
#include <iostream>
#include<string>
#include <string>
#include<queue>
using namespace std;

class Node
{
public:
	int data;
	Node* next;
	Node()
	{
		data = 0;
		next = NULL;
	}
};
Node* recursion(Node* p1, Node* p2, bool flag)
{
	if (p2 != NULL)
	{
		if (flag)
		{
			flag = false;
			p1->next = NULL;
		}
		Node* p3 = p2->next;
		p2->next=p1;

		return recursion(p2,p3,flag);

	}
	else
	{
		
				return p1;
	}
}
int main()
{
	Node* head = new Node();
	Node* p1 = head;
	int i;
	//建立单链表
	for (i = 0; i < 10; i++)
	{
		p1->next = new Node();
		p1 = p1->next;
	}
	//遍历单链表输入数据
	p1 = head;
	for (i = 0; i < 10; i++)
	{
		p1->data = i;
		p1 = p1->next;
	}
	//正序遍历
	p1 = head;

	while (p1->next != NULL)
	{
		cout << p1->data;
		p1 = p1->next;
	}
	cout << "\n";
	//倒序遍历
	p1 = head;

	Node* head1 = recursion(p1, p1->next,true);
	p1 = head1;

	while (p1->next != NULL)
	{
		cout << p1->data;
		p1 = p1->next;
	}
	
}

	



